/*树套数
* 1.树套树
    一棵树套着另一棵树 线段树套平衡树、权值线段树套线段树等


* 2.每一个线段树节点内再多存储一个multiset，表示这个区间内的平衡树
*/

#define DEBUG
#pragma GCC optimize("O1,O2,O3,Ofast")
#pragma GCC optimize("no-stack-protector,unroll-loops,fast-math,inline")
#pragma GCC target("avx,avx2,fma")
#pragma GCC target("sse,sse2,sse3,sse4,sse4.1,sse4.2,ssse3")


#include <iostream>
#include <set>
using namespace std;

const int N=50010, INF=0x3f3f3f3f;

struct node{
    int l, r;
    multiset<int> s;
} tree[N<<2];
int n, m;
int w[N];

void build(int u, int l, int r)
{
    tree[u]={l, r};
    tree[u].s.insert(INF); tree[u].s.insert(-INF);
    for(int i=l; i<=r; i++) tree[u].s.insert(w[i]);
    if(l==r) return; //区间叶节点
    int mid=l+r>>1;
    build(u<<1, l, mid);
    build(u<<1|1, mid+1, r);
}

void modify(int u, int pos, int x)
{
    tree[u].s.erase(tree[u].s.find(w[pos])); //删除原值
    tree[u].s.insert(x); //插入新值
    if(tree[u].l == tree[u].r) return;
    int mid=tree[u].l+tree[u].r>>1;
    if(pos<=mid) modify(u<<1, pos, x);
    else modify(u<<1|1, pos, x);
}

int query(int u, int l, int r, int x) //节点id 查询区间 x
{
    if(l <= tree[u].l && tree[u].r <= r) {
        auto it=tree[u].s.lower_bound(x); //x的位置
        --it;
        return *it;
    }
    int mid=tree[u].l+tree[u].r>>1, ans=-INF;
    if(l<=mid) ans=max(ans, query(u<<1, l, r, x));
    if(r>mid) ans=max(ans, query(u<<1|1, l, r, x));
    return ans;
}

signed main()
{
    #ifdef DEBUG
        freopen("./in.txt","r",stdin);
    #else
        ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    #endif

    scanf("%d%d", &n, &m);
    for(int i=1; i<=n; i++) scanf("%d", &w[i]);
    build(1, 1, n);

    while(m--)
    {
        int op, a, b, x;
        scanf("%d%d%d", &op, &a, &b);
        if(op==1)  // pos x
            modify(1, a, b);
        
        else { // l r x
            scanf("%d", &x);
            printf("%d\n", query(1, a, b, x));
        }
    }
    return 0;
}
